The present invention relates to computer systems and, more specifically, to a method for partitioning a buffer cache.
Most data processing systems include both volatile and nonvolatile memory devices. In general, volatile memory devices, such as random access memory, provide faster access times than nonvolatile memory devices, such as magnetic or optical disks. However, nonvolatile memory is generally less expensive and less susceptible to data loss.
To take advantage of the persistent nature of nonvolatile memory, an object, such as a data item in a database system, is typically stored on nonvolatile memory (e.g. in a data block on a disk) until the data item is required by a particular process of the database system. To take advantage of the speed of volatile memory, a copy of the data block that contains the data item is loaded into volatile memory when the data item is required by a particular process of the database system. Once the data block is loaded into volatile memory, the process can quickly access and make changes to the copy of the data item. At some later point in time, the copy of the updated data item is written back to the database in order to reflect the changes that were made by the process.
For example, in a database system, a section of volatile memory known as a buffer cache is generally used by processes for accessing and manipulating information contained within the database. In order for a process to access or change data that is stored in the database, a copy of the data block that contains the data item is first loaded from the database into the buffer cache. After the data block is loaded in the buffer cache the process can then quickly access and manipulate the copied data version. At some later point in time, the contents of the buffer cache is written back to the database in order to reflect any changes that were previously made to the copied data version.
Typically, the buffer cache includes multiple buffers that are shared among one or more processes that are executing on a database server. When a process executes a transaction that requires a change to a data item within a data block, that is not already present within the buffer cache, the data block that contains the data w item is loaded into a buffer in the buffer cache. Any changes are then made to the data within the buffer.
Because the buffer cache contains a fixed amount of memory, a limited number of buffers are available for processing information. Often the amount of information to be processed exceeds the capacity of the buffers available to hold the information (i.e. data blocks). Once the buffer cache is full, storing new data in the buffer cache requires replacing data that already resides in the buffers within the buffer cache with the new data. In order to manage the limited number of available buffers, several replacement strategies have been developed. These replacement strategies determine which of the buffers currently residing in the buffer cache are to be overwritten with the new data (i.e. cached out).
Over the years, many different replacement strategies have been developed to increase efficiency. The most common of these strategies include replacing the least recently used (LRU) data, replacing the data that has been in the buffer the longest (First-In/First-Out, or FIFO), or replacing the newest data in the buffer (Last-In/First-Out, or LIFO). Each of these methods has both advantages and disadvantages that greatly depend on the amount of data being processed, the size of the buffer cache and the usage pattern which corresponds to how the data is being accessed.
Most database servers employ a single buffer cache. A drawback with using a single buffer cache is that only a single replacement strategy can be used for the entire set of buffers within the buffer cache. Using a single replacement strategy in a database system can be very inefficient when differently sized tables are accessed using different usage patterns. This inefficiency occurs because different usage patterns and differently sized tables can require distinct replacement strategies for efficient caching.
For example, FIG. 1 depicts a database system 100 in which an order table 104, an employee table 106, and a stock table 108 are accessed through a single buffer cache 102. Order table 104 contains a record of each order and contains more data blocks than can fit within the buffers of buffer cache 102 at any one time. Order records are constantly being added to the end of order table 104. Therefore, it would be efficient to only keep in the buffer cache 102 the buffers that contain information from data blocks that are currently at the end of the order table 104.
Conversely, stock table 108 comprises all of the stock items for sale and is small enough to fit within the number of buffers contained in buffer cache 102. As stock items are retrieved on a frequent basis, it would be efficient to keep all data blocks of the entire stock table 108 within the buffers of buffer cache 102 at all times.
On the other hand, employee table 106 contains the address of each employee and is referenced very infrequently. Once an employee record is accessed it is normally not accessed again for a very long period of time. Therefore, it would be efficient to swap-out these buffers soon after an access completes so that another operation can use the buffer.
Because the tables of database system 100 have different caching requirements, a single replacement scheme cannot efficiently manage the replacement requirements associated with each of the tables. However, because data base system 100 contains only a single buffer cache 102, the single replacement strategy for the buffer pool must be applied to all tables within database system 100 regardless of their size and usage patterns.
To address the inefficiencies associated with a single buffer cache, database servers can divide the buffer cache into multiple sub-cache areas. By using multiple sub-cache areas, each sub-cache can maintain its own individual replacement strategy that may differ from the replacement strategies associated with other sub-cache areas. Therefore, different replacement strategies can be used for different table based upon the memory disk address of the data blocks that are associated with a particular table. However, by using multiple sub-cache areas, data blocks, based on their nonvolatile memory disk address, are statically assigned to a particular sub-cache area and therefore can only be cached into buffers that are located within the particular sub-cache area.
Therefore, in such a database system, although multiple sub-cache areas provide for individual replacement strategies, a particular replacement strategy must be used for all data blocks that are assigned to a particular sub-cache area. This mapping restricts a particular table to a particular replacement strategy based on where its associated data blocks are located on disk. Thus, because data blocks are statically assigned to a specific sub-cache area based on its nonvolatile memory disk address, a particular sub-cache area or specific replacement strategy cannot be dynamically chosen for a particular table based on its access or usage pattern.
Therefore, based on the foregoing, it is clearly desirable to provide a mechanism for dynamically mapping data blocks to replacement strategies based on the associated table""s access or usage patterns.
The present invention provides a method and apparatus for partitioning a buffer cache for dynamically mapping data blocks with a particular replacement strategy based on the associated table""s access and/or usage patterns.
According to the method, a buffer cache in a computer system is managed by dividing the buffer cache into multiple buffer pools. In managing the buffer cache, when a data item is requested, it is first determined whether the requested data item is stored in a buffer within the buffer cache. If the requested data item is not stored in a buffer in the buffer cache, then a particular buffer pool in the buffer cache is dynamically selected for storing the requested data item. Once the particular buffer pool is selected, the requested data item is stored into a buffer in the particular buffer pool.
According to another aspect of the invention, a hash table is provided that contains hash chains that link to all the buffers that are contained in the multiple buffer pools. Using the hash chains, the it can be determined whether a requested data item has been stored in a buffer within the multiple buffer pools.
According to another aspect of the invention a hint parameter, which identifies a particular reason as to why a particular object associated with the requested data item is being accessed, is used to select the particular buffer pool for storing the requested data item.